#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
int wh[5005];
int pc[105][105];
int flag=0;
struct node{
    int x;
    int jl;
    node(int c,int jl1):x(c),jl(jl1){}
    bool operator<(const node & y)const{
        return jl>y.jl;
    }
};
    int n,m,k,s,t;
struct anode{
    int x;
    int jl;
    bool wh1[105];
    int zjl;
    anode(int c,int jl1):x(c),zjl(jl1){
        jl=zjl+jl1;
        for(int i=1;i<=k;i++)wh1[i]=0;
    }
    bool operator<(const anode & y)const{
        return jl>y.jl;
    }
};
int jl[500];
int bj[500];
priority_queue<node>q;
priority_queue<anode>q1;
vector<node>v[500];
ll ans=0x3f3f3f3f;
int main(){
    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;i++)cin>>wh[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            cin>>pc[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(!pc[wh[y]][wh[x]]){
              v[x].push_back(node(y,z));
        }
         if(!pc[wh[x]][wh[y]]){
            v[y].push_back(node(x,z));
         }
    }//修改的话需要分为两个图。反向距离不考虑文化，正向文化冲突不建图。
    for(int i=1;i<=n;i++){
        jl[i]=0x3f3f3f3f;
    }
    jl[t]=0;
    q.push(node(t,0));
    while(!q.empty()){
        node f=q.top();
        q.pop();
        bj[f.x]=1;
        for(int i=0;i<v[f.x].size();i++){
            if(bj[v[f.x][i].x])continue;
            if((f.jl+v[f.x][i].jl)<jl[v[f.x][i].x]){
                jl[v[f.x][i].x]=f.jl+v[f.x][i].jl;
                q.push(node(v[f.x][i].x,f.jl+v[f.x][i].jl));
            }
        }
    }
    anode qdd(s,0);
    qdd.wh1[wh[s]]=1;
    q1.push(qdd);
    while(!q1.empty()){
        anode f=q1.top();
        q1.pop();
        if(f.jl>ans)break;
        if(f.x==t){
            flag=1;
            if(ans>f.zjl)ans=f.zjl;
            continue;
        }
        for(int i=0;i<v[f.x].size();i++){
            int now=v[f.x][i].x;
            int bj1=0;
            for(int j=1;j<=k;j++){
                if(pc[wh[now]][j]&&f.wh1[j]){
                    bj1=1;
                    break;
                }
            }
            if(bj1)continue;
            if(!f.wh1[wh[v[f.x][i].x]]&&f.zjl+v[f.x][i].jl+jl[v[f.x][i].x]<ans){
                anode an(v[f.x][i].x,f.zjl+v[f.x][i].jl);
                for(int j=1;j<=k;j++){
                    an.wh1[j]=f.wh1[j];
                }
                an.wh1[wh[v[f.x][i].x]]=1;
                q1.push(an);
            }
        }
    }
    if(flag)cout<<ans;
    else cout<<-1;
    return 0;
}